package leetcode_121_140;

import java.util.*;

public class partition_131 {
    /**
     * 将一个字符串  s 分割成一些子串，使每个子串都是 回文串 。
     * 返回 s 所有可能的分割方案。
     */
    public List<List<String>> partition(String s) {
        /**
         * 类如"aab"
         * ["a","a","b"],["aa","b"]
         * 想法是，先利用中心扩散法，记录每个坐标以及以该坐标为起始字母的所有回文串的结尾坐标
         * 遍历回文串的所有可能，类推第二个第三个进行组合
         * 15ms
         * 官解也就11ms，就不做更改了
         */
        char[]chars=s.toCharArray();
        HashMap<Integer,Set<Integer>>map=new HashMap<>();
        //记录每个坐标以及以该坐标为起始字母的所有回文串的结尾坐标
        for(int i=0;i<chars.length;i++){
            Set<Integer> end=new HashSet<>();
            //自身也算回文串
            end.add(i);
            map.put(i,end);
            int l=i-1,r=i+1;
            //中心扩散
            //奇数长度的回文串
            while(l>-1 && r<chars.length){
                if(chars[l]==chars[r]){
                    map.get(l).add(r);
                    l--;
                    r++;
                } else
                    break;
            }
            //偶数长度的回文串
            if (i!=chars.length-1 && chars[i] == chars[i + 1]) {
                map.get(i).add(i+1);
                l=i-1;r=i+2;
                while (l > -1 && r < chars.length) {
                    if (chars[l] == chars[r]) {
                        map.get(l).add(r);
                        l--;
                        r++;
                    } else
                        break;
                }
            }
        }
        function(chars,0,map);
        return ans;
    }
    List<List<String>>ans=new ArrayList<>();

    List<String>combin=new ArrayList<>();   //实时组合
    /**
     * 递归组合所有可能性
     */
    void function(char[] chars,int index,HashMap<Integer,Set<Integer>>map){
        if(index==chars.length){
            ans.add(new ArrayList<>(combin));
            return;
        }
        for(int end:map.get(index)){
            String str=new String(chars, index, end+1-index);
            combin.add(str);
            function(chars,end+1,map);
            combin.remove(combin.size()-1);
        }
    }


    /**
     * 高解10ms
     */
    private final List<List<String>> ans2 = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    public List<List<String>> partition2(String s) {
        this.s = s;
        dfs(0);
        return ans2;
    }

    private boolean isPalindrome(int left, int right) {
        while (left < right)
            if (s.charAt(left++) != s.charAt(right--))
                return false;
        return true;
    }

    private void dfs(int i) {
        if (i == s.length()) {
            ans2.add(new ArrayList<>(path)); // 复制 path
            return;
        }
        for (int j = i; j < s.length(); ++j) { // 枚举子串的结束位置
            if (isPalindrome(i, j)) {
                path.add(s.substring(i, j + 1));
                dfs(j + 1);
                path.remove(path.size() - 1); // 恢复现场
            }
        }
    }
}
